public class SortingAlgorithm {
    public static void main(String[] args) {
        int[] nums = {9,1,5,8,3,7,4,6,2};

        //调用冒泡排序初级版
//        BubbleSort(nums);
        //调用冒泡排序
//        BubbleSort(nums);
        //调用冒泡排序优化算法
//        BubbleSort2(nums);
        //调用简单选择排序算法
//        SelectSort(nums);
        //调用直接插入排序算法
//        InsertSort(nums);
        //调用希尔排序算法
//        ShellSort(nums);
        //调用快速排序算法
//        QuickSort(nums,0,nums.length - 1);
        //调用归并排序算法
//        MergeSort(nums,0,nums.length - 1);


        //输出排序后的数组
        System.out.print("[");
        for (int num = 0 ; num < nums.length ; num++) {
            if (num != nums.length - 1) {
                System.out.print(nums[num] + ",");
            }else {
                System.out.print(nums[num] + "]");
            }
        }
    }

    //快速排序算法
    //时间复杂度为O(nlogn)
    public static void QuickSort(int[] nums,int low,int high) {
        //由于要递归调用 所以也要传入需要排序的范围
        //定义左右指针和基准值和中间变量middle
        int i,j,temp,middle;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //将第一个元素设为基准值
        temp = nums[low];
        while (i < j) {
            //先看右边 依次往左递减
            while ((nums[j] >= temp) && (i < j)) {
                j--;
            }
            //再看左边 依次向右递增
            while ((nums[i] <= temp) && (i < j)) {
                i++;
            }
            //此时满足从右开始找到比基准小的 从左开始找到比基准大的
            if (i < j) {
                //利用中间变量将两个数字交换
                middle = nums[i];
                nums[i] = nums[j];
                nums[j] = middle;
            }
        }
        //最后将基准值和i与j相等索引的数值交换
        nums[low] = nums[i];
        nums[i] = temp;

        //递归调用左半数组
        QuickSort(nums,low,j - 1);
        //递归调用右半数组
        QuickSort(nums,j + 1,high);
    }

    //归并排序算法
    //时间复杂度为O(nlogn)
    //主函数
    public static void MergeSort(int[] nums,int low,int high) {
        //当子序列中只有一个元素时结束递归
        if (low < high) {
            //划分子序列
            int mid=(low + high)/2;
            //对左侧子序列进行递归排序
            MergeSort(nums, low, mid);
            //对右侧子序列进行递归排序
            MergeSort(nums, mid+1, high);
            //合并
            Merge(nums, low, mid, high);
        }
    }
    //归并部分
    public static void Merge(int[] nums,int low,int mid,int high) {
        //定义合并数组
        int[] array = new int[high - low + 1];
        //定义第一段序列的起始下标
        int i = low;
        //定义第二段序列的起始下标
        int j = mid + 1;
        //定义合并序列的起始下标
        int k = 0;
        //对两段序列从左至右扫描 依次将较小值插入合并数组
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                //插入合并数组
                array[k] = nums[i];
                i++;
                k++;
            }else {
                array[k] = nums[j];
                j++;
                k++;
            }
        }
        //如果此时第一段序列中还有值则直接插入合并数组
        while (i <= mid) {
            array[k] = nums[i];
            i++;
            k++;
        }
        //同理
        while (j <= high) {
            array[k] = nums[j];
            j++;
            k++;
        }
        //将合并数组复制到原来数组中
        for (int x = 0 ; x < array.length ; x++) {
            nums[x + low] = array[x];
        }
    }

    //希尔排序算法
    //时间复杂度为O(nlogn)到O(n^2)之间
    public static void ShellSort(int[] nums) {
        //定义步长
        int stride = nums.length / 2;
        int i,j;
        //定义中间变量
        int temp;
        //当步长大于或者等于1时继续进入循环
        while (stride >= 1) {
            for (i = stride ; i < nums.length ; i++) {
                //默认第一个元素是被插入的元素 用中间变量保存起来
                temp = nums[i];
                //通过步长连接的前一个元素
                j = i - stride;
                //如果前一个元素大于后一个元素
                while (j >= 0 && nums[j] > nums[i]) {
                    //所有元素后移
                    nums[i] = nums[j];
                    //寻找前一个步长连接的元素
                    j -= stride;
                }
                //确保插入位置存在 而且是在j-=stride的基础上 所以插入位置应该为j+stride
                nums[j + stride] = temp;
            }
            //改变步长
            stride = stride / 2;
        }
    }

    //直接插入排序算法
    //时间复杂度为O(n^2) 但是优于简单排序算法的O(n^2)
    public static void InsertSort(int[] nums) {
        //之所以循环从1开始是因为 默认0号位元素已经放好位置
        for (int i = 1 ; i < nums.length ; i++) {
            //保存每次需要插入的那个数
            int key = nums[i];
            //在已经排好的子序列中从后往前查找 定位到排序好的子序列中最后一位
            int j = i - 1;
            //如果检索到的数字大于key 则把所有元素右移给所插入元素提供位置
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            //确保插入位置存在而且是在j--的基础上 所以插入原位置应该为j+1
            nums[j + 1] = key;
        }
    }

    //简单选择排序算法
    //时间复杂度为O(n^2) 但是优于冒泡排序算法的O(n^2)
    public static void SelectSort(int[] nums) {
        int i,j,min;
        for (i = 0 ; i < nums.length ; i++) {
            //将当前下标定义为最小值下标
            min = i;
            //循环之后的数据
            for (j = i + 1 ; j < nums.length ; j++) {
                //如果有小于当前最小值的关键字
                if (nums[j] < nums[min]) {
                    //将此关键字的下标赋值给min
                    min = j;
                }
            }
            //走完一趟循环后如果min不等于i 说明找到了新的最小值 所以要进行交换
            if (i != min) {
                swap(nums, i, min);
            }
        }
    }

    //冒泡排序优化
    /*
    如果待排序的序列是{2,1,3,4,5,6,7,8,9} 除了第一和第二需要交换外 别的都是正常的顺序
    交换了1 2后 序列已经有序 但是算法仍然对后面的每个循环都执行一遍 尽管没有交换数据
    但是之后的大量比较还是大大地多余了
    当i=2时 我们已经对9 8，8 7，7 6，...，3 2做了比较 没有任何数据交换 这就说明此时序列已经有序了
    不需要再继续后面的循环判断工作了
     */
    public static void BubbleSort2(int[] nums) {
        //定义标记变量 记录有无进行数据交换 初始化为有数据交换
        boolean flag = true;
        for (int i = 0 ; i < nums.length && flag; i++) {
            //每一趟排序前先设为false 若上一趟排序并未进行数据交换则在该趟排序开始的判断语句就会退出外层循环 排序结束
            flag = false;
            for (int j = nums.length - 2 ; j >= i ; j--) {
                if (nums[j] > nums[j + 1]){
                    swap(nums,j,j + 1);
                    //若进行了数据交换则把标记变量设为true
                    flag = true;
                }
            }
        }
    }

    //冒泡排序算法
    //时间复杂度为O(n^2)
    public static void BubbleSort(int[] nums) {
        for (int i = 0 ; i < nums.length ; i++) {
            for (int j = nums.length - 2 ; j >= i ; j--) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    //冒泡排序初级版
    /*
    严格来说 不能算是标准冒泡排序算法 因为它不满足 两两比较相邻记录
    的冒泡排序思想 它更应该是最最简单的交换排序而已 它的思路就是让每一个关键字
    都和它后面的每一个关键字比较 如果大则交换 这样第一位置的关键字在一次循环后
    一定变成最小值 这个算法的效率是非常低的
     */
    public static void BubbleSort0(int[] nums) {
        for (int i = 0 ; i < nums.length ; i++) {
            for (int j = i + 1 ; j < nums.length ; j++) {
                //升序排列 若前一个元素大于后一个元素
                if (nums[i] > nums[j]) {
                    swap(nums, i, j);
                }
            }
        }
    }

    //数组两元素的交换
    public static void swap(int[] nums,int i,int j) {
        //定义中间变量用来交换两个元素
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
